/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/subsets
   @Language: C++
   @Datetime: 17-03-13 14:38
   */

// Method 1 recursion
class Solution {
	void subsetcore(vector<int> &nums,int pos,
		vector<vector<int> > &vs, vector<int> &v){
		if (pos==nums.size()){
			vs.push_back(v);		// get one subset
			return;
		}
		v.push_back(nums[pos]);		// select this element
		subsetcore(nums,pos+1,vs,v);
		v.pop_back();				// not select
		subsetcore(nums,pos+1,vs,v);
	}
public:
	/**
	 * @param S: A set of numbers.
	 * @return: A list of lists. All valid subsets.
	 * Tip: eacho element has two state: to be selected and not
	 */
	vector<vector<int> > subsets(vector<int> &nums) {
		// write your code here
		vector<vector<int> > vs;
		vector<int> v;
		sort(nums.begin(),nums.end());
		subsetcore(nums,0,vs,v);
		return vs;
	}
};


// Method 2 loop
class Solution {
public:
	/**
	 * @param S: A set of numbers.
	 * @return: A list of lists. All valid subsets.
	 *
	 * Tip: all subsets count: 2^n (include null)
	 * sketch : set { 1, 2, 3 }
	 * [ ]
	 * [ ] [ ] -> [ ] [1]
	 * [ ] [1] [ ] -> [ ] [1] [2] [1,2]
	 * [ ] [1] [2] [1,2] [ ] -> [ ] [1] [2] [1,2] [3] [1,3] [2,3] [1,2,3]
	 */
	vector<vector<int> > subsets(vector<int> &nums) {
		// write your code here
		vector<vector<int> > vs(1);
		sort(nums.begin(),nums.end());
		for (int i=0; i<nums.size(); ++i){
			int size = vs.size();
			for (int j=0; j<size; ++j){
				vs.push_back(vs[j]);
				vs.back().push_back(nums[i]);
			}
		}
		return vs;
	}
};
